package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 9:35 2020/8/19
 * @Description 回文子串
 * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串
   具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 */

import java.util.Arrays;

public class CountSubstrings {

    /**
     * 这个与最长回文子串不同的是，只需要从内到外判断这个是不是一个回文子串，不用计算长度，只计算个数
     * 因此使用的boolean 使用count计数
     * 如果当前i j 指向的值是相等的，并且i和j之间的长度为不大于3（包含i和j）或者dp[i+1][j-1]为true
     * if s.charAt(i) == s.charAt(j)&&(i-j<=2||dp[i+1][j-1])    dp[i][j] = true  count++
     *
     */
    public int countSubstrings(String s) {
        if (s.length() <= 1) return s.length();
        int count = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = s.length() - 1; i >=0; i--) {
            for (int j = i ; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j) && (j-i<=2|| dp[i + 1][j - 1]) ) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }
}
